/*
 * Amos Kittelson 
 * COP3503 - Computer Science 2
 * Assignment 3 - Railroad Building
 * Due 6 July 2010 (Extended due to military duty)
 */

// Note: Path Compression was not implemented since each Union
// links to the first set added in the disjoint set


public class DisjointSet {

	Edge[] ds;
	
	// Constructor
	DisjointSet (int setSize){
		ds = new Edge[setSize];		
	}
	
	// As Edges are processed they are assigned
	// an id in order of input. Store the edge
	// in the array index by the id number
    public void addElement(Edge edge){
    	ds[edge.getIndex()] = edge;
    }
    
    // get the Edge at a particular index in the array
    public Edge getElement (int element){
    	return ds[element];
    }

    // Union method to merge sets
	public void Union(Edge parent, Edge element){
	   	ds[element.getIndex()] = parent.getObject();
	}
		
	public int Find(Edge edge){
		// Follows the index's element to its parent and
		// returns the parents index.
		// The count variable makes sure we don't get stuck
		// in a cycle.
		
		// The maximum number of indices we'll ever need to check is 
		// the size of the array.
		int count = ds.length;
		
		// used for moving through an index to its parent index
		int testIndex = edge.getIndex();
		
		// Loop through the array until the id number of the Edge
		// matches the array index number.
		while (ds[testIndex].getIndex() != edge.getIndex() && count >= 0){
			testIndex = ds[testIndex].getIndex();
			count--;
		}
		
		// if count == 0 then there wasn't a parent
		if (count == 0)
			return -1;
		else
			return ds[testIndex].getIndex();
	}
	
	// Each Edge has a start and an end vertex. Adding another Edge
	// with Vertices that are already in the set would create a cycle.
	// This method checks the set to see if BOTH Vertices exist
	// in ANY other start or end Edges
	public int Find(Vertex v){
		
		boolean debug = false;
		
		for (Edge e : ds){
			if (e != null){
				if (debug) System.out.println("Comparing:" + v + " against:" + e);
				
				// TODO: Change Vertex comparison from String to Object
				// if (e.getStart() == v || e.getEnd() == v)
				
				// Compare the labels to see if the Vertex is already in the set
				if (e.getStart().getLabel().equals(v.getLabel())							
					|| e.getEnd().getLabel().equals(v.getLabel())){
					
						if (debug) System.out.println("Krustal: Found match");
						
						// if the same Vertex is already in the set then return
						// its index
						return e.getIndex();
				}	
			}
			
		}
		
		// if the Vertex was not found anywhere in the set then return -1
		return -1;
	}
	
	// Return the size of the set
	public int getSize(){
		return ds.length;
	}
	
	// Print out all Edges in the set
	public String arrayToString(int startingPoint){
		
		if (startingPoint + 1 < ds.length)
			return this.toString(startingPoint) + " " + this.arrayToString(startingPoint + 1);
		else
			return this.toString(startingPoint);
	}
	
	// TODO: Check necessity of toString valueOf
	public String toString (int element){
		return String.valueOf(ds[element]);
	}
}
